/* 
 * Jump Game
 */

#include "../func.h"

bool canJump(vector<int> &nums)
{
    int reach = 1;
    for (int i = 0; i < reach && reach < nums.size(); ++i)
    {
        reach = max(reach, i + 1 + nums[i]);
    }
    return reach >= nums.size();
}

bool canJump2(vector<int> &nums)
{
    vector<int> f(nums.size(), 0);
    f[0] = 0;
    for (int i = 1; i < nums.size(); ++i)
    {
        f[i] = max(f[i - 1], nums[i - 1]) - 1;
        if (f[i] < 0)
            return false;
    }
    return f[nums.size() - 1] >= 0;
}